# 给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。
#  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
#  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
#  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#
#  示例 1:
# 输入: prices = [1,2,3,0,2]
# 输出: 3
# 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
#
#  示例 2:
# 输入: prices = [1]
# 输出: 0
from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # size = len(prices)
        # # dpHaveStock[i] 表示第 i 天结束，手上有股票能获得的最大利润
        # # dpNoClod[i] 表示第 i 天结束，手上没有股票且处于冷冻期(即恰在第i天时卖出股票)能获得的最大利润
        # # dpNoStock[i] 表示第 i 天结束，手上没有股票且不是处于冷冻期(即在第i天前已经卖出股票)能获得的最大利润
        # dpNoStock, dpNoStockCold, dpHaveStock = [0] * size, [0] * size, [-prices[0]] * size
        # for i in range(1, size):
        #     dpNoStock[i] = max(dpNoStock[i - 1], dpNoStockCold[i - 1])  # 当天结束手上没有股票
        #     dpNoStockCold[i] = dpHaveStock[i - 1] + prices[i]  # 当天结束处于冷冻期
        #     dpHaveStock[i] = max(dpHaveStock[i - 1], dpNoStock[i - 1] - prices[i])  # 当天结束手上还持有股票
        # return max(dpNoStock[-1], dpNoStockCold[-1])

        # 空间优化写法
        dpNoStock, dpNoStockCold, dpHaveStock = 0, 0, -prices[0]
        for price in prices[1:]:
            tmpNoStock = max(dpNoStock, dpNoStockCold)
            tmpNoStockCold = dpHaveStock + price
            tmpHaveStock = max(dpHaveStock, dpNoStock - price)
            dpNoStock, dpNoStockCold, dpHaveStock = tmpNoStock, tmpNoStockCold, tmpHaveStock
        return max(dpNoStock, dpNoStockCold)


if __name__ == "__main__":
    prices = [1, 2, 3, 0, 2]
    print(Solution().maxProfit(prices))
